package gold.digger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/2/24.
 */
public class LC40 {

    class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List<Integer> valList = new ArrayList<Integer>(Arrays.asList());
            List<List<Integer>> res = new ArrayList<>();
            // 从小到大排序
            Collections.sort(valList);
            List<Integer> curCombination = new LinkedList<>();//便于递归
            dfs(valList, target, 0, curCombination, res);
            return res;
        }

        /**
         * DFS循环遍历主方法
         *
         * @param valList
         * @param target
         * @param curPos
         * @param curCombination
         */
        public void dfs(List<Integer> valList, int target, int curPos, List<Integer> curCombination, List<List<Integer>> res) {
            if (target == 0) {
                res.add(copyArray(curCombination));
                return;
            }

            //选取当前值
            for (int i = curPos; i < valList.size(); i++) {
                //prune branches 做剪枝处理
                if (target < valList.get(i)) break; //valList已经升序排列，当前已经不满足条件，越往后累计更不满足条件了~~
                curCombination.add(valList.get(i));
                dfs(valList, target - valList.get(i), i + 1, curCombination, res);//此处原代码dfs传入下标为curPos，应该为i
                curCombination.remove(curCombination.size() - 1);   //此处原代码敲错了，敲成valList.size,run之后修正。
            }
        }

        public List<Integer> copyArray(List<Integer> ori) {
            List<Integer> copy = new ArrayList<>();
            for (Integer val : ori) {
                copy.add(val);
            }
            return copy;
        }

    }

    class Solution_old_fashion {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            return combinationSumRecur(candidates, target, 0);
        }

        public List<List<Integer>> combinationSumRecur(int[] candidates, int target, int start) {
            List<List<Integer>> result = new ArrayList<>();

            if (target <= 0 || null == candidates || candidates.length <= 0) {
                return result;
            }

            for (int i = start; i < candidates.length; i++) {
                if (i > start && candidates[i] == candidates[i - 1]) {
                    continue;
                }

                if (candidates[i] == target) {
                    List<Integer> curCombList = new ArrayList<>();
                    curCombList.add(candidates[i]);
                    result.add(curCombList);
                    continue;
                }

                if (candidates[i] > target) {
                    continue;
                }

                List<List<Integer>> subResult = combinationSumRecur(candidates, target - candidates[i], i + 1);
                for (List<Integer> curCombination : subResult) {
                    curCombination.add(candidates[i]);
                }
                result.addAll(subResult);
            }

            return result;
        }
    }


    public static void main(String[] args) {
        LC40 an = new LC40();
        int[] arr = {2, 5, 2, 1, 2};
        int target = 5;

//        System.out.println(an.combinationSum2(arr, target));
    }

}
